package LinkedList;
//删除链表的倒数第 N 个结点

public class remove_nth_node_from_end_of_list {
    static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    //给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null||head.next==null){
            return null;
        }

        // 思路过程：先得到链表长度size，然后再利用size-n 就可以将题目转为：删除第size-n个节点，而不是倒数第n个节点
        int size=0;
        ListNode cur1=head;
        while (cur1!=null){
            cur1=cur1.next;
            size++;
        }
        int num=size-n;
        ListNode cur=head;
        //这里来到了倒数第n+1个节点的位置 准备进行删除
        for (int i = 1; i < num; i++) {
            cur=cur.next;
        }
        // n+1-->n-->n-1
        //删除的是头节点
        if(num==0){
            return head.next;
        }
        //删除的是尾节点
        if(n==1){
            cur.next=null;
        }else {
            ListNode next = cur.next.next;
            cur.next = next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        ListNode head2=new ListNode(2);
/*        ListNode head3=new ListNode(3);
        ListNode head4=new ListNode(4);
        ListNode head5=new ListNode(5);*/
        head.next=head2;
//        head2.next=head3;
//        head3.next=head4;
//        head4.next=head5;
        removeNthFromEnd(head,2);
    }
}
